package hihocode;

import java.util.Scanner;

//基因工程
//将给定的DNA串的前K个字符和后K个字符修改为相等
public class GeneticEngineer {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		scanner.nextLine();
		String string;
		int k;
		for (int i = 0; i < testCase; i++) {
			string = scanner.nextLine();
			k = scanner.nextInt();
			scanner.nextLine();
			process(string, k);
		}
		scanner.close();
	}
	
	private static void process(String string, int k){
		if(string == null){
			return;
		}
		int length = string.length();
		int res = 0;
		if(k <= length / 2){
			for(int i = 0; i < k; i++){
				if(string.charAt(i) != string.charAt(length - k + i)){
					res++;
				}
			}
			System.out.println(res);
			return;
		}
//		//如果k > n / 2
		char[] chas = string.toCharArray();
//		//后k个字符起点的下标
		int postStart = length - k;
//		for(int i = postStart; i < k; i++){
//			if(chas[i - postStart] == chas[postStart + i] && chas[i] != chas[i - postStart]){
//				System.out.println(i + " " + postStart);
//				chas[i] = chas[i - postStart];
//				res++;
//			}
//		}
//		System.out.println("res:" + res);
//		for(int i = 0; i < k; i++){
//			if(chas[i] != chas[postStart + i]){
//				res++;
//			}
//		}
//		System.out.println(res);
		
		
		//详细思路见http://www.cnblogs.com/boring09/p/4373492.html
		//主要就是一个循环，因为0... n - k == n - k ... 2 * n - 2 * k
		//而n - k ... 2 * n - 2 * k = n - k...2 * n - 2 * k
		//所以需要循环出现
		for (int i = 0; i < postStart; i++) {
			int[] count = new int[4];
			for (int j = i; j < length; j += postStart) {
				if (chas[j] == 'A') {
					count[0]++;
				} else if (chas[j] == 'T') {
					count[1]++;
				} else if (chas[j] == 'C') {
					count[2]++;
				} else if (chas[j] == 'G') {
					count[3]++;
				}
			}
			//统计所有应该相等中的字符不同的个数，要想最小，就让ATCG变成出现次数最多的
			//出现最多的记为maximum
			int maximum = 0;
			for (int j = 0; j < 4; j++) {
				maximum = Math.max(maximum, count[j]);
				res += count[j];
			}
			//res是所有的和，比如A  2，C  2，T  3， G  1.
			//最后我们将所有的变成T，所以要让和减去T的次数
			res -= maximum;
		}
		System.out.println(res);
	}
}
